package 每日一题;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-10
 **/

public class No441排列硬币 {

    /**
     * 你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，
     * 其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
     * 给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。
     *
     * 示例 1：
     * 输入：n = 5
     * 输出：2
     * 解释：因为第三行不完整，所以返回 2 。
     * 示例 2：
     * 输入：n = 8
     * 输出：3
     * 解释：因为第四行不完整，所以返回 3 。
     *
     * 提示：
     * 1 <= n <= 231 - 1
     */

    public int arrangeCoins(int n) {

        /**
         * 等差数列 [n*(n-1)*d/2] + n * a1
         */

        // n^2 + n - 200 = 0
        // [-1+√(b^2 - 4ac)] / 2

        double c1 = Math.sqrt(1 + (long)8 * (long)n);

        int i = (int) (-1 + c1) / 2;

        return i;
    }

    public static void main(String[] args) {
        No441排列硬币 n = new No441排列硬币();
        int result = n.arrangeCoins(8);
        System.out.println(result);
    }

}
